package com.cat.graphTheory;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-ii/description/
 * @create 2025/9/24 19:37
 * @since JDK17
 */

public class Solution31 {
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length, m = moveTime[0].length;
        int[][] dis = new int[n][m];
        int[] d = new int[]{-1, 0, 1, 0, -1};
        for (var a : dis) {
            Arrays.fill(a, Integer.MAX_VALUE);
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        heap.add(new int[]{0, 0, 0, 1});
        dis[0][0] = 0;
        while (!heap.isEmpty()) {
            var u = heap.poll();
            if (u[2] > dis[u[0]][u[1]]) {
                continue;
            }
            if (u[0] == n - 1 && u[1] == m - 1) {
                return u[2];
            }
            for (int i = 0; i < 4; i++) {
                int nx = u[0] + d[i], ny = u[1] + d[i + 1];
                if (nx == -1 || nx == n || ny == -1 || ny == m) {
                    continue;
                }
                int cost = Math.max(u[2], moveTime[nx][ny]) + u[3]; // 到达下一个位置
                if (cost < dis[nx][ny]) {
                    dis[nx][ny] = cost;
                    heap.add(new int[]{nx, ny, cost, 3 - u[3]});
                }
            }
        }

        return 0;
    }
}
